Consens de mostra aleatòria

Un conjunt de dades amb molts valors atípics als quals s'ha d'ajustar una línia.

Línia ajustada amb RANSAC; els valors atípics no influeixen en el resultat.

El consens de mostra aleatòria (RANSAC) és un mètode iteratiu per estimar paràmetres d'un model matemàtic a partir d'un conjunt de dades observades que conté valors atípics, quan els valors atípics no s'han d'atorgar cap influència en els valors de les estimacions. Per tant, també es pot interpretar com un mètode de detecció atípic. És un algorisme no determinista en el sentit que produeix un resultat raonable només amb una certa probabilitat, amb aquesta probabilitat augmentant a mesura que es permeten més iteracions. L'algorisme va ser publicat per primera vegada per Fischler i Bolles a SRI International el 1981. Van utilitzar RANSAC per resoldre el problema de determinació de la ubicació (LDP), on l'objectiu és determinar els punts de l'espai que es projecten sobre una imatge en un conjunt de punts de referència amb ubicacions conegudes.

RANSAC utilitza un submostreig aleatori repetit. Una hipòtesi bàsica és que les dades consisteixen en "inliers", és a dir, dades la distribució de les quals es pot explicar per algun conjunt de paràmetres del model, encara que poden estar subjectes a soroll, i "outliers", que són dades que no s'ajusten al model. Els valors atípics poden provenir, per exemple, de valors extrems del soroll o de mesures errònies o hipòtesis incorrectes sobre la interpretació de les dades. RANSAC també assumeix que, donat un conjunt (generalment petit) d'inliers, existeix un procediment que pot estimar els paràmetres d'un model que explica o s'ajusta de manera òptima a aquestes dades.

Exemple

Un exemple senzill és ajustar una línia en dues dimensions a un conjunt d'observacions. Suposant que aquest conjunt conté tant inliers, és a dir, punts que aproximadament es poden ajustar a una línia, com outliers, punts que no es poden ajustar a aquesta línia, un mètode simple de mínims quadrats per a l'ajustament de la línia generalment produirà una línia amb un mal ajust a la línia. les dades incloses les inliers i outliers. El motiu és que s'ajusta de manera òptima a tots els punts, inclosos els atípics. RANSAC, en canvi, intenta excloure els valors atípics i trobar un model lineal que només utilitzi els valors intermedis en el seu càlcul. Això es fa ajustant models lineals a diversos mostrejos aleatoris de les dades i retornant el model que s'ajusta millor a un subconjunt de dades. Com que els inliers tendeixen a estar relacionats de manera més lineal que una barreja aleatòria d'inliers i outliers, un subconjunt aleatori que consta completament d'inliers tindrà el millor ajust al model. A la pràctica, no hi ha cap garantia que un subconjunt d'inliers sigui mostrat aleatòriament, i la probabilitat que l'algorisme tingui èxit depèn de la proporció d'inliers a les dades, així com de l'elecció de diversos paràmetres de l'algorisme.

Aplicacions

L'algorisme RANSAC s'utilitza sovint en visió per ordinador, per exemple, per resoldre simultàniament el problema de correspondència i estimar la matriu fonamental relacionada amb un parell de càmeres estèreo; vegeu també: Estructura a partir del moviment, transformació de característiques invariants d'escala, unió d'imatges, segmentació rígida del moviment.